#include <bits/stdc++.h>

using namespace std;

//差一点点超时。。。
class Solution {
public:
    using LL=long long;
    LL MOD=1e9+7;
    LL rlen,clen;
    LL mans=INT32_MIN;
    void dfs(int r,int c,vector<vector<int>>& grid,LL ans){
        // cout << r << " " << c <<endl;
        ans=ans*grid[r][c];
        if(ans==0 || r==rlen-1 && c==clen-1){
            if(ans>mans){
                mans=ans;
            }
            return ;
        }
        if(c<clen-1){
            dfs(r,c+1,grid,ans);
        }
        if(r<rlen-1){
            dfs(r+1,c,grid,ans);
        }
    }
    int maxProductPath(vector<vector<int>>& grid) {
        rlen=grid.size();
        clen=grid[0].size();
        mans=INT64_MIN;
        dfs(0,0,grid,1);
        return mans<0?-1:mans%MOD;
    }
};



class Solution {
public:
    using LL=long long;
    LL MOD=1e9+7;
    int maxProductPath(vector<vector<int>>& grid) {
        int rlen=grid.size(),clen=grid[0].size();
        vector<vector<LL>> mag(rlen,vector<LL>(clen,0));
        vector<vector<LL>> mng(rlen,vector<LL>(clen,0));     
        mag[0][0]=mng[0][0]=grid[0][0];
        for(int i=1;i<clen;i++){
            mag[0][i]=mng[0][i]=mag[0][i-1]*grid[0][i];
        }
        for(int i=1;i<rlen;i++){
            mag[i][0]=mng[i][0]=mag[i-1][0]*grid[i][0];
        }
        for(int i=1;i<rlen;i++){
            for(int j=1;j<clen;j++){
                if(grid[i][j]>=0){
                    mag[i][j]=max(mag[i-1][j],mag[i][j-1])*grid[i][j];
                    mng[i][j]=min(mng[i-1][j],mng[i][j-1])*grid[i][j];
                }else{
                    mng[i][j]=max(mag[i-1][j],mag[i][j-1])*grid[i][j];
                    mag[i][j]=min(mng[i-1][j],mng[i][j-1])*grid[i][j];
                }
            }
        }
        if(mag[rlen-1][clen-1]<0){
            return -1;
        }else {
            return mag[rlen-1][clen-1]%MOD;
        }
    }
};





int main(){
    vector<vector<int>> v={
        {1,-2,1},
        {1,-2,1},
        {3,-4,1}
        };
    Solution1 s;
    cout << s.maxProductPath(v)<<endl;
 


    return 0;
}